package 二叉树;

import 二叉树.树的最大高度_104.TreeNode;

public class 二叉树的最小深度_111 {
	
	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}
	/*
	最小深度就是根节点到最近叶子节点的路径长度
	和找二叉树的最大深度类似，但是区别如下：
	递归终止条件：
	1.根节点为null时，返回0
	2.根节点左右都null时，返回1
	3.比较 left 和 right 的大小终止条件：返回较小值+1
	但是需要注意的是：
	这样就无法保证root是否是叶子节点了，
	 */
	//深度优先搜索
	public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        if (root.left == null && root.right == null) {
            return 1;
        }

        int min_depth = Integer.MAX_VALUE;
        if (root.left != null) {
            min_depth = Math.min(minDepth(root.left), min_depth);
        }
        if (root.right != null) {
            min_depth = Math.min(minDepth(root.right), min_depth);
        }

        return min_depth + 1;
	}

}
